package com.wcj.test;

import com.wcj.linktable.ListNode;

/**
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 数据范围：10000000≤n,m≤1000000，链表任意值 90≤val≤9
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class 链表相加二 {

    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode tmp1 = ReverseList(head1);
        ListNode tmp2 = ReverseList(head2);
        ListNode result = new ListNode(-1);
        ListNode move = result;
        int access = 0;
        while (tmp1 != null && tmp2 != null){
            int sum = tmp1.val + tmp2.val + access;
            move.next = new ListNode(sum%10);
            move = move.next;
            access = sum/10;
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        while (tmp1 != null){
            int sum = tmp1.val + access;
            move.next = new ListNode(sum%10);
            move = move.next;
            access = sum/10;
            tmp1 = tmp1.next;
        }
        while (tmp2 != null){
            int sum = tmp2.val + access;
            move.next = new ListNode(sum%10);
            move = move.next;
            access = sum/10;
            tmp2 = tmp2.next;
        }
        if (access != 0){
            move.next = new ListNode(access);
        }
        return ReverseList(result.next);
    }

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curHead = head.next;
        ListNode rucTail = head;
        rucTail.next = null;
        while (curHead != null) {
            ListNode tmp = curHead;
            curHead = curHead.next;
            tmp.next = rucTail;
            rucTail = tmp;
        }
        return rucTail;
    }
}
